package com.lwt.codetop.dp;
// 1143. 最长公共子序列

/**
 * 思路：dp
 * 模板题
 */
public class LongestCommonSubsequence {
    public static void main(String[] args) {
        String a = "abcde";
        String b = "ace";
        int res = longestCommonSubsequence(a, b);
        System.out.println(res);
    }

    private static int longestCommonSubsequence(String a, String b) {
        int n = a.length(), m = b.length();
        a = " " + a;
        b = " " + b;
        int[][] f = new int[n + 10][m + 10];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(a.charAt(i) == b.charAt(j)){
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }else {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j]);
                }
            }
        }
        return f[n][m];
    }

}
